Constante de Chaitin

Representação em ASCII da ômega de Chaiting

Em ciência da computação, na sub-área de teoria da informação algorítmica, a constante de Chaitin (número Ômega de Chaitin) ou probabilidade de parada é um número real que informalmente representa a probabilidade de que um programa construído de forma aleatória irá parar. Estes números são formados de uma construção de Gregory Chaitin.

Apesar de haver uma infinidade de probabilidades de parada, é comum usar o letra Ω para nos referirmos a elas como se fossem apenas uma. Porque Ω depende da codificação utilizada no programa, então é chamado as vezes de Construção de Chaitin ao invés de Constante de Chaitin quando não referencia nenhuma codificação específica.

Cada probabilidade de parada é um número real normal e transcendente que não é computável, o que significa que não existe algoritmo para computar aqueles dígitos. De fato, cada probabilidade de parada é uma sequência aleatória de Martin-Löf, representando que não existe algoritmo algum que possa adivinhar de fato seus dígitos.

O contexto

A definição de uma probabilidade de parada remete à existência de funções computáveis universais livres de prefixo. Como uma função, intuitivamente, representa uma linguagem de programação com a propriedade de que nenhum programa válido pode ser obtido como uma extensão apropriada de outro programa válido.

Suponha que F é uma função parcial que recebe um argumento, uma string binária finita, e possivelmente retorna uma única string binária como saída. A função F é chamada computável se existe uma Máquina de Turing que a computa (no sentido de que para qualquer string binária x tal que F(x) = y a máquina de Turing para com y em sua fita quando dada a entrada x).

A função F é chamada universal se a possui a seguinte propriedade: para cada função computável f de uma única variável, existe uma string w de modo que para todo x, F(w x) = f(x); aqui w x representa a concatenação de duas strings w e x. Isso significa que F pode ser usado para simular qualquer função computável de uma variável. Informalmente, w representa um "script" para a função computável f, e F representa um "interpretador" que analisa o script como um prefixo de sua entrada e então executa ele no restante da entrada.

O domínio de F é o conjunto de todas as entradas p em que ele é definido. Para os F que são universais, p podem ser geralmente vistas como ambos uma concatenação de uma parte de um programa e parte de dados, e como um único programa para a função F.

A função F é chamada livre de prefixo se não houver dois elementos p, p′ em seu domínio tal que p′ é uma extensão própria de p. Isso pode ser definido como: o domínio de F é um código livre de prefixo (código instantâneo) no conjunto de strings binárias finitas. Uma maneira simples de aplicar o prefixo livre é usar máquinas das quais a entrada é um fluxo binário de bits que são lidos um por vez. Não existe marcador de fim da cadeia; o fim da entrada é determinado pela máquina universal que decide parar de ler mais bits. Aqui, a diferença entre duas noções de programas mencionados no último parágrafo se tornam claras; uma é facilmente reconhecida por alguma gramática, enquanto a outra requer computação arbitrária para ser reconhecida.

O domínio de qualquer função universal computável é um computavelmente enumerável mas nunca um conjunto computável. O domínio é sempre Turing equivalente ao problema da parada.

Definição

Seja P_F o domínio de uma função computável universal livre de prefixo universal F. A constante Ω_F é então definida como

$\Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}$,

onde $\left|p\right|$ é o tamanho de uma string p. É uma soma infinita que tem uma soma para cada p no domínio de F. O requerimento é que o domínio seja livre de prefixo, juntamente a desigualdade de Kraft, garante que essa soma converge para um número real entre 0 e 1. Se F é uma consequência do contexto então Ω_F pode ser simplesmente denominado Ω, ainda que diferentes funções universais livres de prefixo levam à difrentes valores de Ω.

Relação com o problema da parada

Conhecendo os primeiros $N$ bits de $\Omega$, pode-se calcular o problema da parada para todos os programas de tamanho até $N$. Seja o programa $p$ para qual o problema da parada deve ser resolvido em N bits de tamanho. Em um implementador universal de forma, todos os programas de todos os tamanhos são rodados, até que um número suficiente deles tiverem parado para assim contribuir conjuntamente com probabilidade suficiente para combinar estes primeiros N bits. Se o programa $p$ ainda não parados, então ele nunca irá parar, desde que sua constribuição à probabilidade da parada irá afetar os primeiros N bits. Assim, o problema da parada vai ser resolvido por $p$.

Por causa de muitos problemas pendentes em teoria dos números, como a conjectura de Goldbach são equivalentes à resolver o problema da paradapara programas especiais (que irão basicamente procurar por contraexemplos e para se um for achado), sabendo bits o suficiente da constante de Chaitin irá também significa saber a resposta para esses problemas. Mas como o problema da parada geralmente não é solúvel, e portanto calcular qualquer um exceto os primeiros bits da constante de Chaitin não é possível, isso apenas reduz problemas difíceis para problemas impossíveis, seria como tentar construir uma máquina de oráculo para o problema da parada.

Interpretação como uma probabilidade

O espaço de Cantor é uma coleção de todas as sequencias infinitas de 0s e 1s. A probabilidade de parada pode ser interpretada como a medida de um determinado subconjunto do espaço de Cantor sob a medida de probabilidade no espaço de Cantor. É a partir dessa interpretação que as probabilidades de paradas têm seu nome.

A medida de probabilidade no espaço Cantor, algumas vezes chamada de "medida da moeda justa", é definido tal que para qualquer string binária x o conjunto de sequências que começam com x tem medida 2^−|x|. Isso implica que para cada número natural n, o conjunto de sequências f no espaço de Cantor tal que f(n) = 1 tem medida 1/2, e o conjunto de sequências as quais o n-ésimo elemento é 0 também tem medida 1/2.

Seja F uma função computável universal livre de prefixo. O domínio P de F consiste em um conjunto infinito de strings binárias

$P=\{p_{1},p_{2},\ldots \}$.

Cada uma dessas strings p_i determina um subconjunto S_i do espaço de Cantor; o conjunto S_i contém todas as sequências no espaço de Cantor que começam com p_i. Esses conjuntos são disjuntos porque P é um conjunto livre de prefixo. A soma

$\sum _{p\in P}2^{-|p|}$

representa e medida do conjunto

$\bigcup _{i\in \mathbb {N} }S_{i}$.

Desta forma, Ω_F representa a probabilidade de que selecionado aleatoriamente uma sequência infinita de 0s e 1s que começam com uma cadeia de bits (de algum tamanho finito) que está no domínio de F. É por essa razão que Ω_F é chamado probabilidade de parada.

Propriedades

Cada constante de Chaitin Ω tem as seguintes propriedades:

• É algoritmicamente aleatória. Isso significa que o menor programa para produzir os primeiros n bits de Ω deve ser de tamanho pelo menos n-O(1). Isso porque, como no exemplo de Goldbach, aqueles n bits nos permitem achar exatamente qual programa para entre todos aqueles de tamanho no máximon.
• É um número normal, o que significa que seus dígitos são igualmente distribuidos como se fossem gerados por um lançamento de uma moeda justa.
• Não é um número computável; não há função computável que enumera sua expansão binária, como discutido abaixo.
• É o conjunto de números racionais q tal que q < Ω é computavelmente enumerável; um número real com a propriedade que é chamada número real c.e.-esquerda (computavelmente enumerável à esquerda) em teoria da recursão.
• É o conjunto de números racionais q tal que q > Ω não é computavelmente enumerável.
• Ω é um número aritmético.
• É Turing equivalente ao problema da parada e, assim, ao nível $\Delta _{2}^{0}$ da hierarquia aritmética.

Nem todo conjunto que é Turing equivalente ao problema da parada é uma probabilidade de parada. A mais fina relação de equivalência, equivalência Solovay, pode ser usada para caracterizar a probabilidade de parada entre os reais c.e.-esquerda.

Incomputabilidade

Um número real é chamado calculável se existe um algoritmo que, dado n, retorna os primeiros n dígitos do número. Isto é equivalente à existência de um programa que enumera os dígitos do número real.

Nenhuma probabilidade de parada é computável. A prova desse fato depende de um algoritmo que, dada os primeiros n dígitos de Ω, resolve o problema da parada de Turing por programas de tamanho até n. Uma vez que o problema da parada é indecidível, Ω não pode ser computado.

O algoritmo procede como descrito a seguir. Dado os primeiros n dígitos de Ω e um k≤n, o algoritmo enumera o domínio de F até elementos suficientes do domínio serem encontrados de modo que a probabilidade de que eles representam é dentro do limite de 2^−(k+1) de Ω. Depois deste ponto, nenhum programa adicional de tamanho k pode estar em seu domínio, porque cada um destes iria adicionar^−k para a medida, o que é impossível. Assim, o conjunto de cadeias de comprimento k no domínio é exatamente o conjunto de tais sequências já enumerados.

Teorema da incompletude para probabilidade de parada

Para cada sistema axiomático específico representado consistentemente e eficazmente para números naturais, como os da Aritmética de Peano, existe uma constante N tal qual nenhum bit de Ω depois do N-ésimo pode ser provado ser 1 ou 0 dentor desse sistema. A constante N depende de como o sistema formal [e efetivamente representado, e assim não reflete diramente a complexidade do sistema axiomático. Esse resultado da incompletude é similar ao Teorema da Incompletude de Gödel que mostra que nenhuma forma teórica consistente para aritmética pode ser completa.

Super Ômega

Como mencionado acima, os primeiros n bits da constante Ômega de Gregory Chaitin são aleatórios ou incompreensíveis no sentido de que nós não podemos computá-los por um algoritmo de parada com menos que n-O(1) bits. Entretanto, considere o algoritmo curto, mas nunca um de parada que lista sistematicamente e executa todos os programas possíveis;sempre que um deles é interrompido sua probabilidade é adicionado à saída (inicializada em zero). Depois de um tempo finito os primeiros n bits da saída nunca mais vão mudar (não importa que se desta vez não é computável por um programa de parada). Portanto, há um algoritmo não-parante e curto cuja saída converge (depois de tempo finito) nos primeiros n bits de Ômega. Em outras palavras, os primeiros n bits enumeráveis de Omega são altamente compreensíveis no sentido que são limite computáveis por um algoritmo muito pequeno; eles não são aleatórios com respeito ao conjunto de algoritmos enumerados. Jürgen Schmidhuber (2000) construiu um "Super Ômega" limite computável que num certo sentido é muito mais aleatória do que o limite computável Ômega original, como não se pode comprimir significativamente o Super Ômega por qualquer algoritmo enumerado não-parante.

Ver também

• Complexidade de Kolmogorov
• Teorema da incompletude

Bibliografia

• Calude, Cristian S. (2002). Information and Randomness: An Algorithmic Perspective second ed. [S.l.]: Springer. ISBN 3-540-43466-6 
• Downey, R.; Hirschfeldt, D. (2010). Algorithmic Randomness and Complexity. [S.l.]: Springer-Verlag 
• Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. [S.l.]: Springer 
• Schmidhuber, Jürgen (2002). «Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit». International Journal of Foundations of Computer Science. 13 (4): 587–612. doi:10.1142/S0129054102001291 

Ligações externas

• Omega and why maths has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
• The Limits of Reason, Gregory Chaitin, originally appeared in Scientific American, March 2006.
• Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, by Jürgen Schmidhuber